/// @tags: SAM SegmentTree Set SuffixTree
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <set>
#include <vector>

using namespace std;

namespace BlueQuantum {

typedef pair<int, int> pii;
typedef set<int>::iterator Iter;

int const N = 2e5 + 5, M = 26, INF = 0x3f3f3f3f;

char str[N];
int n, m, lst = 1, tot = 1;
int ans[N], len[N], link[N], ch[N][M], id[N];
set<int> s[N];
vector<int> e[N];
vector<pii> eve[N], q[N];

void dfs(int u) {
  if (id[u]) s[u].insert(id[u]);
  s[u].insert(INF);
  for (vector<int>::iterator i = e[u].begin(), ilim = e[u].end(); i != ilim; ++i) {
    int v = *i;
    dfs(v);
    if (s[u].size() < s[v].size()) s[u].swap(s[v]);
    if (s[v].empty()) continue;
    for (Iter it = s[v].begin(); it != s[v].end(); ++it)
      if (*it != INF) {
        Iter uit = s[u].lower_bound(*it);
        if (*uit != INF) eve[*uit].push_back(make_pair(*it, len[u]));
        if (uit != s[u].begin()) uit--, eve[*it].push_back(make_pair(*uit, len[u]));
      }
    for (Iter it = s[v].begin(); it != s[v].end(); ++it) s[u].insert(*it);
    s[v].clear();
    // set<int>().swap(s[v]);
  }
}

inline void extend(int c, int i) {
  int cur = ++tot, pos = lst;
  lst = cur;
  len[cur] = len[pos] + 1;
  id[cur] = i;
  while (pos != 0 && ch[pos][c] == 0) ch[pos][c] = cur, pos = link[pos];
  if (pos == 0) return link[cur] = 1, void();
  int q = ch[pos][c];
  if (len[q] == len[pos] + 1) return link[cur] = q, void();
  int clone = ++tot;
  memcpy(ch[clone], ch[q], sizeof(ch[q]));
  link[clone] = link[q];
  link[q] = link[cur] = clone;
  len[clone] = len[pos] + 1;
  while (pos != 0 && ch[pos][c] == q) ch[pos][c] = clone, pos = link[pos];
}

struct Node {
  int v, l, r;
} tr[N * 4];

inline void modify(int x, int l, int r, int p, int v) {
  tr[x].v = max(tr[x].v, v);
  if (l == r) return;
  int mid = (l + r) >> 1;
  p <= mid ? modify(x << 1, l, mid, p, v) : modify(x << 1 | 1, mid + 1, r, p, v);
}

inline int query(int x, int l, int r, int L, int R) {
  int mid = (l + r) >> 1;
  if (L <= l && r <= R) return tr[x].v;
  int ans = 0;
  if (L <= mid) ans = max(ans, query(x << 1, l, mid, L, R));
  if (mid < R) ans = max(ans, query(x << 1 | 1, mid + 1, r, L, R));
  return ans;
}

inline int check(int l, int r, int x) { return query(1, 1, n, l + x - 1, r) >= x; }

inline int query(int l, int r) {
  int L = 1, R = r - l + 1;
  while (L <= R) {
    int mid = (L + R) >> 1;
    if (check(l, r, mid)) L = mid + 1;
    else
      R = mid - 1;
  }
  return R;
}

inline int main() {
  cin >> n >> m >> (str + 1);
  reverse(str + 1, str + n + 1);
  for (int i = 1; i <= n; ++i) extend(str[i] - 'a', i);
  for (int i = 2; i <= tot; ++i) e[link[i]].push_back(i);
  dfs(1);
  for (int i = 1, l, r; i <= m; ++i) {
    cin >> l >> r;
    l = n - l + 1, r = n - r + 1;
    q[l].push_back(make_pair(r, i));
  }
  for (int i = 1; i <= n; ++i) {
    for (vector<pii>::iterator j = eve[i].begin(), jlim = eve[i].end(); j != jlim; ++j)
      modify(1, 1, n, j->first, j->second);
    for (vector<pii>::iterator j = q[i].begin(), jlim = q[i].end(); j != jlim; ++j)
      ans[j->second] = query(j->first, i);
  }
  for (int i = 1; i <= m; ++i) cout << ans[i] << '\n';
  return 0;
}

}  // namespace BlueQuantum

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen("/tmp/CodeTmp/testdata.in", "r", stdin);
  freopen("/tmp/CodeTmp/testdata.out", "w", stdout);
#else
  freopen("a.in", "r", stdin);
  freopen("a.out", "w", stdout);
#endif
#endif

  ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
  return BlueQuantum::main();
}
